Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля. Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна. При минимизации по методу Квайна в базисе 1 предполагается, что исходная функция задана в СНДФ. Напомним, что импликанта функции - это некоторая логическая функция, обращаемая в ноль при наборе переменных, на которых сама функция также равна нулю. Поэтому любой минтерм в составе СНДФ, или группа минтермов, соединенных знаками дизъюнкции, являются импликантами исходной НДФ. Первичная или простая импликанта функции - это импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой данной функции. Дизъюнкция простых импликант, ни одну из которых исключить нельзя, называется тупиковой НДФ заданной функции. Некоторые функции имеют несколько тупиковых форм. Тупиковые формы, содержащие наименьшее количество букв, будут минимальными. Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности поглощения какой-то переменной: Fxi  Fxi = F Таким образом, удается снизить ранг термов. Эта процедура проводится до тех пор, пока не останется ни одного члена, допускающего поглощение с каким-либо другим термом. Термы, подвергшиеся поглощению, отмечаются. Неотмеченные термы представляют собой первичные импликанты. Полученное логическое выражение не всегда оказывается минимальным. Поэтому исследуется возможность дальнейшего упрощения. Для этого составляется таблица, в строках которой записываются найденные первичные импликанты, а в столбцах указываются термы исходного уравнения. Клетки этой таблицы отмечаются в случае, если первичная импликанта входит в состав какого-либо терма. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы. В этом методе используются операции неполного склеивания (полным склеиванием, как нам известно, будет:xy  xy = x) и поглощения (x  xy = x). Применяемая в методе Квайна операция неполного склеивания определяется формулой: xy  xy = x  xy  xy. Заметим, что в правой части равенства, кроме члена ч, полученного в результате полного склеивания, остаются оба члена, участвующие в склеивании. Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получается сокращенная дизъюнктивная нормальная форма этой функции, т.е. дизъюнкция всех ее простых импликант. Метод Квайна выполняется в несколько этапов и сокращенную НДФ удобно находить в следующей последовательности. Провести в СНДФ функции все возможные операции склеивания конституент единицы. В результате этого образуются произведения, содержащие (n - 1) букв. Подчеркнем, что склеиваться могут только произведения с одинаковым числом букв. Поэтому после этой процедуры производится операция поглощения, а затем выполняются все возможные склеивания членов с (n - 1) буквой. После этого проводится поглощение членов с (n - 1) буквой и вновь выполняется операция склеивания членов с числом букв, равным (n - 2), и т.д. Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции, заданной таблично. Представим функцию в совершенной дизъюнктивной нормальной форме f(x, y, z) =xyz  xyz  xyz. В правой части полученного выражения можно выполнить только одно склеивание: второго члена с третьим по переменной z. При этом получим f(x, y, z) = xy xyz  xyz  xyz. Произведение xy поглощает члены xyz b xyz: f(x, y, z) = xy xyz. Это выражение является сокращенной дизъюнктивной нормальной формой заданной логической функции, так как дальнейшее применение склеивания и поглощения невозможно. Теперь рассмотрим процедуру минимизации более сложной функции с использованием импликативных матриц. Предположим, что требуется найти мини...